1. Field of the Invention
The present invention relates to a graphic processing device for generating a computer graphics (CG) screen on a display, such as a CRT (Cathode Ray Tube), and in particular to a graphic processing device which divides an object into multiple polygons and performs a geometric process on the polygons, and then for rasterizes pixels that constitute each polygon. More specifically, the present invention pertains to a graphic processing device for performing an anti-aliasing process to remove aliasing at the edges of polygons, and in particular to a graphic processing device for performing anti-aliasing in accordance with a percentage (i.e., a coverage) of sub-pixels, included in a pixel, that are covered by a polygon.
2. Related Art
In accordance with recent technical progression, application fields for computers have expanded. The preparation and processing of graphic forms and images using computers, i.e., computer graphics (CG), is one of examples. Recently, in accordance with improvements in the display capabilities of computers, and functional enhancements of graphic processes, xe2x80x9cthree-dimensional graphicsxe2x80x9d that generate two-dimensional images of three-dimensional objects and display them has been focused on. Three-dimensional graphics is a technique whereby an arithmetic model is employed to represent an optical phenomenon of a three-dimensional object when it is illuminated by a light source, and that performs shading of the surface of the object based on the arithmetic equation model, or that puts a pattern to a two-dimensional image to generate a graphic image that has a more realistic appearance and has three dimensions. The three-dimensional graphic techniques have become more popular for the CAD/CAM in science, engineering, manufacturing and other application fields, and in various software development fields.
The graphic processing system generally comprises a xe2x80x9cgeometry sub-systemxe2x80x9d that is regeared as a front end and a xe2x80x9craster sub-systemxe2x80x9d that is regarded as a back end.
The geometry sub-system is a system for performing a geometric process to determine the position of an object on a computer screen. In the geometry sub-system, generally, an object is treated as a set of multiple polygons (normally triangles), and processing is performed for each polygon. That is, geometric calculations, such as xe2x80x9ccoordinate transformation,xe2x80x9d xe2x80x9cclippingxe2x80x9d and xe2x80x9ccalculation relative to a light source,xe2x80x9d are performed for each vertex that defines a polygon. xe2x80x9cCoordinate transformationxe2x80x9d is a process for transforming the coordinates of each vertex of a provided polygon in accordance with the position of a viewpoint. xe2x80x9cClippingxe2x80x9d is a process for detecting and removing a portion of a polygon that is outside the boundaries of the edge of a computer screen. xe2x80x9cCalculation relative to a light sourcexe2x80x9d is a process for acquiring the luminance of each vertex based on the positional relationship with a light source.
The raster subsystem is a system for generating pixels that constitute an object. The rasterization process is generally performed by interpolating image parameters for all pixels in the polygon, with employing an image parameter that is obtained for each vertex of a polygon. The image parameters are color data represented by RGB and a Z value representing the depth. For the latest three-dimensional graphic process, an f (fog), to express a distance, and a t (texture), to express a material or a pattern on the surface of an object to provide reality, are included as image parameters. These image parameters are also calculated for each pixel.
Almost all data in the computer engineering field are represented as digital values. Therefore, so-called aliasing, which is an undesirable phenomenon, frequently appears during the conversion of an analog phenomenon in the natural world into discontinuous digital values. In computer graphic processing, aliasing is perceived as being the zig-zag edges of a polygon, or as a graphic form that has an inaccurate shape. This phenomenon is also caused because the pixels of a display are too large or the resolution is insufficiently high in comparison with the visual acuity of a person.
The process employed for removing the aliasing phenomenon is generally called anti-aliasing. The anti-aliasing process in the computer graphic field can be performed, for example, by dividing a pixel, which is the minimum unit for a drawing process, into multiple sub-pixels and by re-evaluating image data (color data, etc.) concerning the pixel obtained during the rasterization process. In other words, in the anti-aliasing process, a pixel that is cut across by the edges of polygons is divided into 4xc3x974, 8xc3x978 or 16xc3x9716 sub-pixels, and the value of the color data provided for a pixel is adjusted in accordance with the percentage of sub-pixels covered by a polygon (the sub-pixels to be painted), i.e., the coverage of the sub-pixels.
In the example shown in FIG. 5, a part of a pixel is covered with a polygon having a linear edge. When the pixel is divided into 4xc3x974 sub-pixels, the coverage is 14/16. In the example shown in FIG. 6, a part of a pixel is covered with a polygon having an arced edge. When the pixel is divided into 4xc3x974 sub-pixels, the coverage is 14/16. In these examples, instead of determining the color data for a pixel to be discontinuous values based on whether or not a pixel is covered by a polygon, the graduation should be adjusted in accordance with the extent of the coverage of the pixel. As a result, discontinuity at the edge will be reduced and the display quality will be enhanced. A graduation substantially similar to a natural phenomenon may be added to the edges of the polygon by performing anti-aliasing. For example, a three-dimensional wire frame model generated by CAD can be drawn as a continuous smooth line with no zig-zags. In addition, an image can be drawn for which there is less smearing of color at the edge of a polygon.
For the coverage calculations for acquiring the percentage of sub-pixels covered, whether the sub-pixels of a pixel are positioned inside a polygon, along an edge line, or outside the polygon must be determined. In other words, for the coverage calculation, a processing function (edge function) must be performed to determine the position of each sub-pixel, either above, below or on an edge line that defines the boundary of a polygon.
It would be easily understood by one having ordinary skill in the art that the edge function is represented by geometric calculation expressions that include several terms. Since the edge function processing is conventionally performed by software, fast calculation is difficult. It is preferable for fast anti-aliasing that a specific hardware circuit (e.g., an LSI) be used and that parallel processing be performed. However, the edge function processing involves multiple multiplications and divisions, and a relatively large gate size is required for implementing the hardware that performs such calculation (well known). Therefore, the size of the LSI chip would become larger and accordingly, the manufacturing costs would increase.
It is, therefore, one object of the present invention to provide a superior graphic processing device to perform an anti-aliasing process for removing aliasing that occurs at the edges of polygons.
It is another object of the present invention to provide a superior graphic processing device that performs anti-aliasing in accordance with a percentage (coverage) of the sub-pixels, included in a pixel, that are covered by a polygon.
It is an additional object of the present invention to provide a superior graphic processing device that performs parallel and rapid processing to acquire a coverage required for an anti-aliasing process.
It is a further object of the present invention to provide a superior graphic processing device on which an LSI having a relatively small gate size can be implemented to acquire the coverage required for anti-aliasing.
To achieve the above objects, according to a first aspect of the present invention, a graphic processing device that has a function for calculating a coverage that indicates the percentage of a pixel to be painted, includes: means for providing information relating to an edge line that defines the border between a portion to be painted and a portion not to be painted; a first processing unit for processing an edge function with regard to a pixel coordinate; more than one second processing unit for processing an edge function with regard to a sub-pixel reference for the respective sub-pixels within the pixel; evaluation means for determining, in accordance with output of the first and second processing units, whether the sub-pixel is located above, below, or on the edge line; and coverage calculating means for calculating a coverage for the pixel based on the resultant values of the evaluation means with regard to the respective sub-pixels.
According to a second aspect of the present invention, a graphic processing device that has a function for adjusting a pixel graduation according to a coverage that indicates the percentage of a pixel to be painted, includes: means for providing information relating to an edge line that defines a border between a portion to be painted and a portion not to be painted; means for determining image information for the portion to be painted; a first processing unit for processing an edge function with regard to a pixel coordinate; more than one second processing unit for processing an edge function with regard to a sub-pixel reference for the respective sub-pixels within the pixel; evaluation means for determining, in accordance with output of the first and second processing units, whether the sub-pixel is located above, below, or on the edge line; coverage calculating means for calculating a coverage for the pixel based on the resultant values of the evaluation means performed with regard to the respective sub-pixels; and means for adjusting image information of the pixel according to the obtained coverage.
The second processing unit can be mounted outside the first processing unit.
According to a third aspect of the present invention, a coverage calculating unit that calculates a coverage that indicates the percentage of a pixel within a predetermined area, includes: a first processing unit for receiving coordinate data that defines an edge line of the predetermined area and coordinate data of a pixel, for acquiring an edge function that defines the edge line and outputting a coefficient for the edge function, and for processing the edge function of the pixel and outputting the result; more than one second processing unit for receiving the coefficient of the edge function that defines the edge line, and a sub-pixel reference of the respective sub-pixels within the pixel, and for calculating an edge function of the corresponding sub-pixel and outputting the result; and a determination unit for, by employing a result of the edge function obtained through the first processing unit and the result of the edge function obtained through the respective second processing units, determining whether the sub-pixel is inside or outside the predetermined area.
According to a fourth aspect of the present invention, a coverage calculating unit that calculates a coverage that indicates the percentage of a pixel within a predetermined area, comprises: a first processing unit for receiving coordinate data that defines an edge line of the predetermined area and coordinate data of a pixel, for acquiring an edge function that defines the edge line and outputting a coefficient for the edge function, and for processing the edge function of the pixel and outputting the result; more than one second processing unit for receiving the coefficient of the edge function that defines the edge line, and a sub-pixel reference of the respective sub-pixels within the pixel, and for calculating an edge function of the corresponding sub-pixel and outputting the result; a determination unit for, by employing a result for the edge function obtained through the first processing unit and a result for the edge function obtained through the second processing unit, determining whether the sub-pixel is inside or outside the predetermined area; and a coverage calculating unit for collecting results for all sub-pixels within the pixel and calculating a coverage of the pixel.
The second processing unit can be mounted outside the first processing unit.
The basic principle of the present invention will now be explained in detail.
An equation (i.e., edge function: ef) for a line (edge) that connects two vertexes, V0 (x0, y0) and V1 (x1, y1), of a polygon is expressed as equation (1) below. In equation (1), dx=x1xe2x88x92x0 and dy=y1xe2x88x92y0.
ef=(yxe2x88x92y0)dxxe2x88x92(xxe2x88x92x0)dyxe2x80x83xe2x80x83[Equation 1]
Assume that a point slightly apart from an arbitrary point (x, y) on the line (edge) is (x+xcex94x, y+xcex94y). When the coordinates at this point are substituted into equation (1), the edge function is represented as equation (2).
ef=(yxe2x88x92y0)dxxe2x88x92(xxe2x88x92x0)dx+xcex94ydxxe2x88x92xcex94xdyxe2x80x83xe2x80x83[Equation 2]
Assuming that point (x, y) is pixel coordinates, (x+xcex94x, y+xcex94y) can be sub-pixel coordinates and (xcex94x, xcex94y) can be a sub-pixel reference values. In many cases, each sub-pixel reference is integer times a constant value.
When the edge function for sub-pixel coordinates (x+xcex94x, y+xcex94y), expressed by equation (2), is divided into the base edge function Bef, concerning pixel coordinates (x, y), and the sub-edge function Sef, concerning sub-pixel reference (xcex94x, xcex94y), they are described as equations (3) and (4) below.
Bef=(yxe2x88x92y0)dx+(x0xe2x88x92x)dyxe2x80x83xe2x80x83[Equation 3]
Sefxe2x88x92xcex94ydxxe2x88x92xcex94xdyxe2x80x83xe2x80x83[Equation 4]
When the sum of the values of the edge functions Bef and Sef is substituted into the above equations as a variable of evaluation function LineIOcheck, a lineIO information for a sub-pixel (whether a sub-pixel is located above, below, or on an edge) can be determined (see equation (5)).
IO=LineIOcheck(Bef+Sef)xe2x80x83xe2x80x83[Equation 5]
Generally, sub-pixel references xcex94x and xcex94y are considerably smaller than pixel coordinates x and y, and xcex94x less than  less than x and xcex94y less than  less than y are established. Accordingly, the sub-edge function Sef is considerably smaller than the base edge function Bef.
In the computer engineering field, a small data value can be represented by a narrow bit width, so that the gate size of an LSI which implements the process for a small data value is small. A Bef processing unit that must process a relatively large coordinate value must also be relatively large. For example, a graphics workstation display has a resolution of about 4096=213)xc3x974096 (=213), and x and y coordinates for addressing a pixel require an 18-bit width, 13 bits for an integer portion and 5 bits for a decimal fraction portion. Since the Bef processing unit receives and processes the x and y coordinates that each have an 18-bit width, a large processing unit is required. On the other hand, sub-pixel references xcex94x and xcex94y correspond only to the decimal fraction portion of the pixel coordinates for x and y, so that only a three-bit width is sufficient for 8xc3x978 sub-pixels. That is, since the Sef processing unit processes only three-bit sub-pixel references xcex94x and xcex94y, only a small processing unit is required.
While the Bef processing is performed once for one pixel, the Sef processing must be performed for each of the sub-pixels within a pixel. In addition, taking the sizes of the processing units into consideration, it is very probable according to an packaging technique that a single Bef processing unit and a plurality of Sef processing units can be provided on a single LSI chip.
As previously described, in the coverage calculation, the processing (Bef processing) for the coordinates of one pixel is accompanied by the processing (Sef processing) for 4xc3x974, 8xc3x978 or 16xc3x9716 sub-pixel references. When the edge function is divided into the base edge function portion Bef, concerning the pixel coordinates, and the sub-edge function portion Sef, concerning the sub-pixel reference, and when a plurality of Sef processing units are provided for one Bef processing unit, a high efficiency for the mounting of a single LSI chip can be performed and the implementation of the equivalent coverage calculation capability requires only a small area, so that manufacturing costs can be reduced. Further, since the Bef calculation for a pixel and a plurality of Sef calculations for sub-pixels, which accompanies the Bef calculation, are performed in parallel, the processing speed can be increased.
While in the above description it has been assumed that the edge function was for a linear edge of a polygon, the edge function for an arced edge will be described.
Assume that the edge of a polygon is composed of an arc with a center Vc (xc, yc) and a diameter d. The equation (edge function: cef) for the arc is thus represented as equation (6).                     Cef        =                                            (                              d                2                            )                        2                    -                      {                                                            (                                      x                    -                                          x                      c                                                        )                                2                            +                                                (                                      y                    -                                          y                      c                                                        )                                2                                      }                                              [                  Equation          ⁢                      xe2x80x83                    ⁢          6                ]            
Assume that a point slightly apart from an arbitrary point (x, y) on the arc (edge) is (x+xcex94x, y+xcex94y). When the coordinates at this point are substituted into equation (6), the edge function is represented as equation (7). It should be noted that xxe2x88x92Xc=dx and yxe2x88x92yc=dy.                     Cef        =                                            (                              d                2                            )                        2                    -                      (                                          ⅆ                                  x                  2                                            +                              ⅆ                                  y                  2                                                      )                    -                      {                                          2                ⁢                                  (                                                                                    ⅆ                        x                                            ⁢                                              xe2x80x83                                            ⁢                      Δ                      ⁢                                              xe2x80x83                                            ⁢                      x                                        +                                                                  ⅆ                        y                                            ⁢                                              xe2x80x83                                            ⁢                      Δ                      ⁢                                              xe2x80x83                                            ⁢                      y                                                        )                                            +                              Δ                ⁢                                  xe2x80x83                                ⁢                                  x                  2                                            +                              Δ                ⁢                                  xe2x80x83                                ⁢                                  y                  2                                                      }                                              [                  Equation          ⁢                      xe2x80x83                    ⁢          7                ]            
Assuming that point (x, y) is pixel coordinates, (x+xcex94x, y+xcex94y) can be sub-pixel coordinates and (xcex94x, xcex94y) can be a sub-pixel reference values, as previously described. In many cases, each sub-pixel reference is integer times a constant value.
When the edge function for sub-pixel coordinates expressed by equation (7) is divided into the base edge function Bef, concerning pixel coordinates (x, y), and the sub-edge function Sef, concerning sub-pixel reference (xcex94x, xcex94y), they are described as equations (8) and (9) below.                     Bef        =                                            (                              d                2                            )                        2                    -                      (                                          ⅆ                                  x                  2                                            +                              ⅆ                                  y                  2                                                      )                                              [                  Equation          ⁢                      xe2x80x83                    ⁢          8                ]            xe2x80x83Sef=xe2x88x92{2(dxxcex94x+dyxcex94y)+xcex94x2+xcex94y2}xe2x80x83xe2x80x83[Equation 9]
When the sum of the values of the edge functions Bef and Sef is substituted as a variable of evaluation function CircleIOcheck into the above equations, a circleIO information for a sub-pixel (whether a sub-pixel is located above, below, or on an edge) can be determined (see equation (10)).
IO=CircleIOcheck(Bef+Sef)xe2x80x83xe2x80x83[Equation 10]
Generally, sub-pixel references xcex94x and xcex94y are considerably smaller than pixel coordinates x and y, and xcex94x less than  less than x and xcex94y less than  less than y are established. Accordingly, the sub-edge function Sef is considerably smaller than the base edge function Bef (described above).
In the computer engineering field, a small data value can be represented using a narrow bit width, so that the gate size of an LSI to be implemented for processing a small data value is small. A Bef processing unit that processes a relatively large coordinate value must be relatively large. On the other hand, as the required Sef processing unit is small, a plurality of Sef processing units can be provided for one Bef processing unit (as described above).
As previously described, in the coverage calculation, the processing (Bef processing) for the coordinates for one pixel is accompanied by the processing (Sef processing) of 4xc3x974, 8xc3x978 or 16xc3x9716 sub-pixel references. When the edge function is divided into the base edge function portion Bef, concerning the pixel coordinates, and the sub-edge function portion Sef, concerning the sub-pixel reference, and when a plurality of Sef processing units are provided for one Bef processing unit, an LSI chip having a small area can be designed that has the same coverage calculation capability and a high mounting efficiency, resulting in the reduction of manufacturing costs. Further, since the Bef calculation for a pixel and the Sef calculations for a plurality of sub-pixels, which accompany the Bef calculation, are performed in parallel, the processing speed can be increased.
For the LSI design, it is well known that a small gate size for a computer, i.e., a small mounting area, directly affects the reduction of manufacturing costs. According to the present invention, since a unit for coverage calculation during graphic processing (particularly during a rasterization process) occupies only a small mounting area, the manufacturing costs can be greatly reduced.
In short, according to the present invention, provided is a superior graphic processing device that performs parallel, rapid edge function processing for coverage calculation during an anti-aliasing process.
In addition, according to the present invention, provided is a superior graphic processing device on which can be mounted an LSI having a relatively small gate size that performs coverage calculation for anti-aliasing.